package com.wkh.datastructure.priorityqueue;

import com.wkh.datastructure.queue.Queue;

//优先级队列,基于大顶堆实现优先队列
public class PriorityQueue3<E extends Priority> implements Queue<E> {
    private Priority[] array;
    private int size;
    public PriorityQueue3(int capacity) {
        this.array = new Priority[capacity];
    }

    /**
     * 向队列尾插入值
     *
     * @param value 待插入值
     * @return 插入成功返回true，插入失败返回false
     */
    /**
     * 1.入堆新元素，加入到数组末尾〔索引位置child)
     * 2．不断比较新加元素与它父节点(parent)优先级
     *  -如果父节点优先级低，则向下移动，并找到下一个parent
     *  -直至父节点优先级更高或child==0为止
     */
    @Override//时间复杂度为O(log(n))
    public boolean offer(E value) {
        if (isFull()){
            return false;
        }
        int child = size++;
        int parent = (child - 1) / 2;
        while (child>0&&value.priority()>array[parent].priority()){
            array[child] = array[parent];
            child = parent;
            parent = (child-1)/2;
        }
        array[child] = value;
        return true;
    }

    /**
     * 从队列获取值，并移除
     *
     * @return 如果队列非空返回队头值，否者返回null
     */

    /**
     *1．交换堆顶和尾部元素，让尾部元素出队
     *2．(下潜)
     *  -从堆顶开始，将父元素与两个孩子较大者交换
     *  -直到父元素大于两个孩子，或没有孩子为止
     */
    @Override//时间复杂度为O(log(n))
    public E pool() {
        if (isEmpty()){
            return null;
        }
        swap(0,size-1);
        E e = (E) array[size - 1];
        size--;
        array[size] = null;

        //下潜操作
        down(0);
        return e;
    }

    private void down(int parent) {
        int left = parent*2+1;
        int right = left+1;
        int max = parent;
        if (left<size && array[left].priority() > array[max].priority()){
            max = left;
        }
        if (right<size && array[right].priority() > array[max].priority()){
            max = right;
        }
        if (max!=parent){
            swap(parent,max);
            down(max);
        }
    }

    private void swap(int i, int j) {
        Priority t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    /**
     * 从队头获取值，不移除
     *
     * @return 如果队列非空返回队头值，否则返回null
     */
    @Override
    public E peek() {
        if (isEmpty()){
            return null;
        }
        E e = (E) array[0];
        return e;
    }

    /**
     * 检查队列是否为空
     *
     * @return 空返回true，否则返回false
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 检查队列是否已满
     *
     * @return 满了返回true，否则返回false
     */
    @Override
    public boolean isFull() {
        return size == array.length;
    }
}
